// Buffer cache.
//
// The buffer cache is a linked list of buf structures holding
// cached copies of disk block contents.  Caching disk blocks
// in memory reduces the number of disk reads and also provides
// a synchronization point for disk blocks used by multiple processes.
//
// Interface:
// * To get a buffer for a particular disk block, call bread.
// * After changing buffer data, call bwrite to write it to disk.
// * When done with the buffer, call brelse.
// * Do not use the buffer after calling brelse.
// * Only one process at a time can use a buffer,
//     so do not keep them longer than necessary.


#include "types.h"
#include "param.h"
#include "spinlock.h"
#include "sleeplock.h"
#include "riscv.h"
#include "defs.h"
#include "fs.h"
#include "buf.h"
#include "bucket.h"

struct {
  struct buf buf[NBUF];           // 缓冲区
  struct bucket buckets[HVALUE];  // 哈希桶
} bcache;


void
binit(void)
{
  struct buf *b;
  // 初始缓冲区加载到第一个桶
  int init = 0; 


  // 初始化哈希桶
  for(int i=0; i<=HVALUE-1; ++i) {
    // 初始化每个桶的锁 都命名为bcache
    initlock(&bcache.buckets[i].lock, "bcache");
    
    // 将每个哈希桶的前后结点都指向自己表示为空
    bcache.buckets[i].head.next = &bcache.buckets[i].head;
    bcache.buckets[i].head.prev = &bcache.buckets[i].head;
  }

  // 初始化缓冲区 使用头插法将整个缓冲区都装入第一个桶中（届时再从其中窃取）
  for(b = bcache.buf; b < bcache.buf+NBUF; b++){
    b->next = bcache.buckets[init].head.next;
    b->prev = &bcache.buckets[init].head;
    initsleeplock(&b->lock, "buffer");
    bcache.buckets[init].head.next->prev = b;
    bcache.buckets[init].head.next = b;
  }
}

// 获取到所有桶的锁 相当于获得缓冲区的一把大锁
void acquire_all_bucket_lk(){
  for(int i=0; i<HVALUE; ++i){
    acquire(&bcache.buckets[i].lock);
  }
}

// 释放所有桶的锁 相当于 释放缓冲区的一把大锁
void release_all_bucket_lk(){
  for(int i=0; i<HVALUE; ++i){
    release(&bcache.buckets[i].lock);
  }
}

// 检查当前时刻缓冲区中是否还有可用缓存块 如果确认没有则panic
void check_no_buffer() {
  // 获取所有锁保证原子性查找
  acquire_all_bucket_lk();

  // 遍历所有桶的缓存块 寻找是否有可用的buffer
  for(int i=0; i<HVALUE; ++i){
    // 遍历当前桶的缓存块 寻找是否有可用的buffer
    for(struct buf* cur = bcache.buckets[i].head.next; cur != &bcache.buckets[i].head; cur = cur->next){
      // 判断当前块是否可用 但凡存在一个可用的缓存块 都能确定现在不属于no buffer状态
      if(cur->refcnt == 0){
        // 释放所有锁并返回
        release_all_bucket_lk();
        return;
      }
    }
  }

  panic("bget: no buffers");
}

// 获取当前时间戳
uint get_ts() {
  int ts;
  acquire(&tickslock);
  ts = ticks;
  release(&tickslock);
  return ts;
}


// Look through buffer cache for block on device dev.
// If not found, allocate a buffer.
// In either case, return locked buffer.
static struct buf*
bget(uint dev, uint blockno)
{
  struct buf *b;

  // 不再获取全局锁 改为获取缓存块号映射的哈希桶的锁
  int id = HFUN(blockno);
  acquire(&bcache.buckets[id].lock);

  // 扫描哈希桶，查找具有给定设备和扇区号（kernel/bio.c）的缓存块
  // Is the block already cached?
  for(b = bcache.buckets[id].head.next; b != &bcache.buckets[id].head; b = b->next){
    // 如果存在这样的缓存块，bget将获取缓存块的睡眠锁。然后Bget返回锁定的缓冲区。
    if(b->dev == dev && b->blockno == blockno){
      // 更新缓存块引用计数
      b->refcnt++;

      // 更新缓存块的最近使用时间 保证缓存驱逐时LRU
      b->ts = get_ts();

      // 释放桶的锁 再获得缓存块的睡眠锁
      release(&bcache.buckets[id].lock);
      acquiresleep(&b->lock);
      return b;
    }
  }

  // 如果对于给定的扇区没有缓冲区，bget必须进行基于LRU的缓存驱逐
  // Not cached.
  // Recycle the least recently used (LRU) unused buffer.
  b = 0;
  
  // 从当前桶开始遍历每个哈希桶
  for(int j = 0, i; j < HVALUE; ++j){
    // 获取当前遍历的桶编号
    i = (id + j) % HVALUE;

    // 在遍历到不是当前桶的桶时 获取这个桶的锁
    if(j != 0){
      acquire(&bcache.buckets[i].lock);
    }

    // 遍历当前桶的缓存块 使用LRU算法进行缓存驱逐
    for(struct buf* cur = bcache.buckets[i].head.next; cur != &bcache.buckets[i].head; cur = cur->next){
      // 首先判断当前块是否可用
      if(cur->refcnt == 0){
        // 根据LRU算法，总是选取最近未使用过的缓存块进行缓存驱逐
        if(b == 0 || cur->ts < b-> ts){
          b = cur;
        }
      }
    }

    // 找到了一个合理的缓存块 则加载其信息
    if(b != 0){
      // 如果这个块不属于当前桶
      if(j != 0){
        // 将这个缓存块从其原本的桶中删除并释放这个桶的锁
        b->next->prev = b->prev;
        b->prev->next = b->next;
        release(&bcache.buckets[i].lock);

        // 使用头插法将这个块加入当前桶
        b->next = bcache.buckets[id].head.next;
        b->prev = &bcache.buckets[id].head;
        bcache.buckets[id].head.next->prev = b;
        bcache.buckets[id].head.next = b;
      }

      // 编辑缓存块元数据以记录新设备和扇区号
      b->dev = dev;
      b->blockno = blockno;

      // b->valid = 0的布置确保了bread将从磁盘读取块数据，而不是错误地使用缓冲区以前的内容
      b->valid = 0;
      b->refcnt = 1;
      
      // 更新最近使用时间
      b->ts = get_ts();
 
      // 释放当前桶的锁并获取获取缓存块的睡眠锁 返回这个缓存块
      release(&bcache.buckets[id].lock);
      acquiresleep(&b->lock);
      return b;
    }
    // 没有找到合适的缓存块 则归还锁并去下一个桶寻找
    else {
      // 如果此时遍历的桶不是当前桶（buckets[id]），则记得释放这个桶的锁
      /* 
      关于释放锁的时机：
        我们持有当前桶也即(buckets[id])的锁是为了修改或增添其缓存块,因此其释放时机是在创建新缓存块之后
        我们持有本轮遍历到的桶(buckets[i])的锁是为了从其中查找并窃取缓存块，因此在我们从其中取出缓存块以后或者查找完毕之后即可释放锁
      */
      if(j != 0){
        release(&bcache.buckets[i].lock);
      }
    }


  }

  /* 没有在缓冲区中搜索到可用的缓存块
     事实上，在允许bget和brelease可以同步访问整个缓冲区时（即没有大锁）
     可能会出现已经搜索过的位置又被其他CPU释放的情况发生
     这时会导致报 no buffers并不是真正的no buffers
  */

  // 再次原子性地遍历缓冲区判断是否还有可用缓存块 如果还有则重新调用bget获取 否则panic
  check_no_buffer();
  return bget(dev, blockno);

}


// 调用bget为给定扇区（kernel/bio.c）获取缓冲区
// Return a locked buf with the contents of the indicated block.
struct buf*
bread(uint dev, uint blockno)
{
  struct buf *b;
  b = bget(dev, blockno);
  // 如果缓冲区需要从磁盘进行读取，bread会在返回缓冲区之前调用virtio_disk_rw来执行此操作
  if(!b->valid) {
    virtio_disk_rw(b, 0);
    b->valid = 1;
  }
  return b;
}

// 如果缓冲区被修改过，则必须在释放缓冲区之前调用bwrite将更改的数据写入磁盘
// Write b's contents to disk.  Must be locked.
void
bwrite(struct buf *b)
{
  if(!holdingsleep(&b->lock))
    panic("bwrite");
  virtio_disk_rw(b, 1);
}

// 释放缓冲区
// Release a locked buffer.
// Move to the head of the most-recently-used list.
void
brelse(struct buf *b)
{
  // 如果没持有缓冲区的睡眠锁 则panic
  if(!holdingsleep(&b->lock))
    panic("brelse");

  // 释放睡眠锁
  releasesleep(&b->lock);

  // 更新缓存块引用计数
  b->refcnt--;

  // 更新缓存块的最近使用时间 保证缓存驱逐时LRU
  b->ts = get_ts();
}

void
bpin(struct buf *b) {
  // 不再获取全局锁 改为获取缓存块映射的哈希桶的锁
  int id = HFUN(b->blockno);
  acquire(&bcache.buckets[id].lock);
  b->refcnt++;
  release(&bcache.buckets[id].lock);
}

void
bunpin(struct buf *b) {
  // 不再获取全局锁 改为获取缓存块映射的哈希桶的锁
  int id = HFUN(b->blockno);
  acquire(&bcache.buckets[id].lock);
  b->refcnt--;
  release(&bcache.buckets[id].lock);
}


